题解 P1044@洛谷 【栈】

主要原理:卡特兰数

首先,根据题意,自己枚举了一些比较小的时候的结果,感觉很熟悉,突然发现——

这不就是卡特兰数吗?!

紧接着我企图百度百科找到题解卡特兰数数列,用于打表输出。

这是被我打了的表:

const long long catalan[] = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452};

综合题意,得程序:

#include <iostream>
using namespace std;

const long long catalan[] = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452};

int main()
{
	int n;
	cin>>n;
	cout<<catalan[n]<<endl;
	return 0;
}

打表数据出处:https://baike.baidu.com/item/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/6125746?fr=aladdin#1